from collections import deque
from typing import List


class Solution:
    """
    方法：使用拓扑排序或DFS检测图中是否有环来判断课程是否能够完成
    Args:
        numCourses: int, 课程总数
        prerequisites: List[List[int]], 课程依赖关系列表，每个元素[a,b]表示要完成a需要先完成b
    Returns:
        bool, 如果所有课程都能完成返回True，否则返回False
    Time: O(V+E), V是课程数量，E是依赖关系数量
    Space: O(V+E), 需要存储邻接表和入度数组/颜色数组
    """
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # 构建邻接表和入度数组
        adj = [[] for _ in range(numCourses)]
        in_degree = [0] * numCourses
        for a, b in prerequisites:
            adj[b].append(a)
            in_degree[a] += 1
        # 初始化队列，入度为 0 的课程入队
        queue = deque()
        for i in range(numCourses):
            if in_degree[i] == 0:
                queue.append(i)
               
        # 拓扑排序
        count = 0
        while(queue):
            node = queue.popleft()
            count += 1
            for neighbor in adj[node]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)
        return count == numCourses
    
    """
    方法：使用深度优先搜索（DFS）检测图中是否有环来判断课程是否能够完成
    Args:
        numCourses: int, 课程总数
        prerequisites: List[List[int]], 课程依赖关系列表，每个元素[a,b]表示要完成a需要先完成b
    Returns:
        bool, 如果所有课程都能完成返回True，否则返回False
    Time: O(V+E), V是课程数量，E是依赖关系数量
    Space: O(V+E), 需要存储邻接表和颜色数组
    """
    def canFinish1(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        g =[[] for _ in range(numCourses)]
        for a, b in prerequisites:
            g[b].append(a)
        colors = [0] * numCourses
        def dfs(x: int) -> bool:
            colors[x] = 1  # x 正在访问中
            for y in g[x]:
                if colors[y] == 1 or colors[y] == 0 and dfs(y):
                    return True # 找到了环
            colors[x] = 2 # x 完全访问完毕
            return False # 没有找到环
        for i, c in enumerate(colors):
            if c == 0 and dfs(i):
                return False # 有环
        return True